package exercise;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution7 {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();

            Arrays.sort(nums);

            // 固定一个数
            int cur = 0, len = nums.length;
            while (cur < len - 2) {
                // 如果固定的数大于 0, 那么后面的数相加都不可能是负数
                if (nums[cur] > 0) {
                    break;
                }
                
                // 双指针
                int l = cur + 1, r = len - 1;
                System.out.println(nums[cur] + " " + nums[l] + " " + nums[r]);
                while (l < r) {
                    int target = -nums[cur];
                    int sum = nums[l] + nums[r];
                    if (sum < target) {
                        l++;
                    } else if (sum > target) {
                        r--;
                    } else {
                        // 添加进结果
                        ans.add(new ArrayList<Integer>(Arrays.asList(nums[cur], nums[l], nums[r])));
                        // 缩小范围
                        l++; r--;
                        // 去重
                        while (l < r && nums[l] == nums[l-1]) l++;
                        while (l < r && nums[r] == nums[r+1]) r--;
                    }
                }
                // 去重
                cur++;
                while (cur < len - 2 && nums[cur] == nums[cur-1]) cur++;
            }

            return ans;
        }
    }